(6 puntos) Teoría

1.1(1 punto) ¿Para qué se utiliza una Expresión Regular y cuál es su relación con las Definiciones Regulares?

1.2(1 punto) Enumere las precondiciones que debe cumplir una gramática para ser LL(1).

1.3(1 punto) ¿Que condición debe cumplir una tabla Look Ahead (LA) para que la gramática asociada sea LLK?

1.4(1 punto) Defina formalmente los términos: alfabeto, cadena, lenguaje, y gramática

1.5(1 punto) ¿Qué es una gramática ambigua?

1.6(1 punto) ¿Para qué se utiliza el Lema de Bombeo?

(14 puntos) Desarrollo

2.1(2 puntos) Construya un AFND para la siguiente expresión regular utilizando sólo las reglas definidas en el algoritmo de Thompson

(b|b)⁺abb (a|b)^*

2.2(2 puntos) Construya un AFD para la expresión regular del ejercicio anterior a partir del AFND generado con el algoritmo de Thompson, utilizando para ello el algoritmo estudiado en clases.

2.3(2 puntos) Obtenga la gramática regular del autómata finito obtenido en el ejercicio anterior, utilizando el algoritmo estudiado en clases

2.4(3 puntos) Escriba un AF que acepte el siguiente lenguaje:

L={ w ∈ {a,b}^* | la subsecuencia aab no aparece en w}

2.5(5 puntos) Dados los siguientes analizadores léxico y sintáctico:

class CalcLexer extends Lexer;

WS  :   (' '
    |   '\t'
    |   '\n'
    |   '\r')
        { $setType(Token.SKIP); }
    ;

LPAREN: '(' ;

RPAREN: ')' ;

STAR:   '*' ;

PLUS:   '+' ;

SEMI:   ';' ;

protected
DIGIT
    :   '0'..'9' ;

INT :   (DIGIT)+ ;


class CalcParser extends Parser;
options {
    importVocab=CalcLexer;
}

tokens {
}

expr:   mexpr (PLUS mexpr)* EOF
    ;

mexpr
    :   atom (STAR atom)*
    ;

atom:   INT    ;

Modifique el analizador sintáctico para que genere un árbol de sintáxis abstracta. Escriba con la sintaxis de ANTLR un analizador sintáctico para el árbol que indique por resultado de la expresión aritmética. Escriba una clase

Main

con un método

public static void main(string[] args)

que permita la ejecución del interpretador recibiendo como parámetro la expresión a evaluar.